/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        // 利用完全二叉树的性质
        if(root == nullptr)
            return 0;

        TreeNode *left = root->left, *right = root->right;
        int leftDepth = 0, rightDepth = 0;
        while(left)
        {
            leftDepth++;
            left = left->left;
        }
        while(right)
        {
            rightDepth++;
            right = right->right;
        }
        if(rightDepth == leftDepth)
            return (2 ^ leftDepth) - 1;

        return 1 + countNodes(root->left) + countNodes(root->right);



        // 按照普通二叉树迭代法
        // if(root == nullptr)
        //     return 0;
        // int ret = 0;
        // queue<TreeNode*> q;
        // q.push(root);
        // while(!q.empty())
        // {
        //     int n = q.size();
        //     for(int i = 0; i < n; i++)
        //     {
        //         ret++;
        //         TreeNode *cur = q.front();
        //         q.pop();
        //         if(cur->left)
        //             q.push(cur->left);
        //         if(cur->right)
        //             q.push(cur->right);
        //     }
        // }
        // return ret;


        // 按照普通二叉树递归求法
        // if(root == nullptr)
        //     return 0;
        // return 1 + countNodes(root->left) + countNodes(root->right);
    }
};